package A1_链表;

public class LC_707设计链表 {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    class MyLinkedList {
        int size;
        ListNode head;
        ListNode dummyhead=new ListNode();
        public MyLinkedList() {
            size=0;
            head=new ListNode(0);
            dummyhead.next=head;
        }

        //获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1
        public int get(int index) {
            if(index<0||index>=size)
                return -1;//不合法情况
            ListNode cur=dummyhead.next;
            //找到第index指针cur，返回cur值即可
            while(index>=0){
                cur=cur.next;
                index--;
            }
//            for(int i=0;i<=index;i++)
//                cur=cur.next;
            return cur.val;
        }
        //头插法
        public void addAtHead(int val) {
            addAtIndex(0,val);
        }
        //尾插法
        public void addAtTail(int val) {
            addAtIndex(size,val);
        }
        //将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
        // 如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。
        // 如果 index 比长度更大，该节点将 不会插入 到链表中。
        public void addAtIndex(int index, int val) {
            if(index>size)
                return;
            if(index<0)
                index=0;
            ListNode newnode=new ListNode(val);
            ListNode cur=dummyhead;
//            for(int i=0;i<=index;i++)
//                cur=cur.next;
            while(index>=0){
                cur=cur.next;
                index--;
            }
            newnode.next=cur.next;
            cur.next=newnode;
            size++;
        }
        //如果下标有效，则删除链表中下标为 index 的节点。
        public void deleteAtIndex(int index) {
            if(index<0||index>=size)
                return;
            ListNode cur=dummyhead;
            while(index>=0){
                cur=cur.next;
                index--;
            }
//            for(int i=0;i<=index;i++)
//                cur=cur.next;
            cur.next=cur.next.next;
            size--;
        }
    }
}
